home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Libris Britannia 4
/
science library(b).zip
/
science library(b)
/
TECHNICA
/
COMPUTER
/
H254.ZIP
/
IRITSM3S.ZIP
/
IRIT
/
BOOL2LOW.C
< prev
next >
Wrap
C/C++ Source or Header
|
1991-11-10
|
38KB
|
964 lines
/*****************************************************************************
* "Irit" - the 3d polygonal solid modeller. *
* *
* Written by: Gershon Elber Ver 0.2, Mar. 1990 *
******************************************************************************
* Module to handle the low level boolean operations. The routines in this *
* module should be accessed from "bool-hi.c" module only. *
* Note the polygons of the two given objects may not be convex, and must *
* be subdivided into convex ones in the boolean upper level routines (module *
* bool-hi.c). All the routines of this module expects objects with convex *
* polygons only although they might return objects with non convex polygons, *
* but marked as so (via polygons CONVEX tags - see Irit.h)! *
* Because Bool-low.c module was too big, it was subdivided to two: *
* Bool1Low.c - mainly handles the intersecting polyline between the oprnds. *
* Bool2Low.c - mainly handles the polygon extraction from operands given the *
* polyline of intersection and the adjacencies (see ADJACNCY.C) *
*****************************************************************************/
/* #define DEBUG If defined, return intersection POLYLINE object. */
/* #define DEBUG2 If defined, defines some printing routines. */
/* #define DEBUG3 Print messages to entry/exit from routines. */
#ifdef __MSDOS__
#include <alloc.h>
#include <dos.h>
#endif /* __MSDOS__ */
#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <string.h>
#include "program.h"
#include "allocate.h"
#include "booleang.h"
#include "booleanl.h"
#include "convex.h"
#include "geomat3d.h"
#include "intrnrml.h"
#include "objects.h"
static int TestAinB(VertexStruct *V, PolygonStruct *Pl, int AinB);
static PolygonStruct *ClipOpenLoopFromPoly(PolygonStruct *Pl,
InterSegListStruct *OLoop, int AinB);
static void ClosedLoopsToPolys(InterSegListStruct *PClosed, PolygonStruct *Pl);
static VertexStruct *CutPolygonAtRay(PolygonStruct *Pl, PointType Pt);
static CombineClosedLoops(PolygonStruct *Pl, InterSegListStruct *PClosed,
int AinB);
static void PushAdjOnStack(PolygonStruct *Pl, PolygonStruct *AdjStack[],
int *StackPointer);
static PolygonStruct *ChainPolyLists(PolygonStruct *Pl1, PolygonStruct *Pl2);
#ifdef DEBUG2
static void PrintVrtxList(VertexStruct *V);
static void PrintInterList(InterSegmentStruct *PInt);
#endif /* DEBUG2 */
/*****************************************************************************
* Test on which side of polygon Pl, given Point V is, and according to *
* the requirement (AinB) returns TRUE/FALSE. *
* If test on V fails, we tries the next one V -> Pnext until success... *
*****************************************************************************/
static int TestAinB(VertexStruct *V, PolygonStruct *Pl, int AinB)
{
int In;
RealType Distance;
VertexStruct *VHead = V;
do {
Distance = Pl -> Plane[0] * V -> Pt[0] +
Pl -> Plane[1] * V -> Pt[1] +
Pl -> Plane[2] * V -> Pt[2] + Pl -> Plane[3];
In = Distance > 0.0;
V = V -> Pnext;
}
while (ABS(Distance) < EPSILON && V != NULL && V != VHead);
if (ABS(Distance) < EPSILON)
FatalError("TestAInB: Failed to find non coplanar point.\n");
return (In && AinB) || (!In && !AinB); /* I wish I had logical XOR ... */
}
/*****************************************************************************
* Convert an inter loop into an open vertex list. *
*****************************************************************************/
VertexStruct *InterLoopToVrtxList(InterSegmentStruct *PIHead)
{
VertexStruct *VHead, *V;
VHead = V = AllocVertex(0, 0, NULL, NULL);
PT_COPY(VHead -> Pt, PIHead -> PtSeg[0]);
while (PIHead != NULL) {
V -> Pnext = AllocVertex(0, 0, NULL, NULL);
V = V -> Pnext;
PT_COPY(V -> Pt, PIHead -> PtSeg[1]);
PIHead = PIHead -> Pnext;
}
V -> Pnext = NULL;
return VHead;
}
/*****************************************************************************
* Clip an open loop from a polygon: *
* 1. Clip the section (S) of the polygon between the two loop end points and *
* replace it by the loop itself. *
* 2. If the polygon formed from S and the loop should be in the output *
* (as tested by AinB) return that polygon. Otherwise return NULL. *
* The open loop itself (excluding the header OLoop) is freed. *
* Note it is assumed (ordered by the sorting routines above) that the open *
* loop starts from the second end back to first: *
* *
* L1-----------------------L2 *
* | | *
* |L0 |L3 *
* *---------------*-------+----*-------------*----+-----------* *
* P0 P1 P2 P3 P0 *
*****************************************************************************/
static PolygonStruct *ClipOpenLoopFromPoly(PolygonStruct *Pl,
InterSegListStruct *OLoop, int AinB)
{
int GenClipPoly; /* TRUE if needs to form polygon from S & OLoop. */
VertexStruct *VStart, *VEnd, *VEnd1, /* Corresponds to L0 and L3... */
*ClipPoly, /* The clipped element from polygon. */
*PLoop, *PRevLoop, /* The loop itself as vertex list. */
*PLoopEnd, *PLoopEnd1, *Ptemp1, *Ptemp2;
InterSegmentStruct *PISeg, *PItemp;
PolygonStruct *ClipPl;
#ifdef DEBUG3
printf("Enter ClipOpenLoopFromPoly\n");
#endif /* DEBUG3 */
PISeg = OLoop -> PISeg;
VStart = PISeg -> V[0];
while (PISeg -> Pnext != NULL) PISeg = PISeg -> Pnext;
VEnd = PISeg -> V[1];
if (VStart == NULL || VEnd == NULL)
FatalError("ClipOpenLoopFromPoly: None open loop\n");
VEnd1 = VEnd; /* Find the pointer thats points on VEnd. */
while (VEnd1 -> Pnext != VEnd) VEnd1 = VEnd1 -> Pnext;
PLoop = InterLoopToVrtxList(OLoop -> PISeg);/* Make vertex list out of it*/
PLoopEnd = PLoop; /* Prepare pointer on last vertex. */
while (PLoopEnd -> Pnext != NULL) PLoopEnd = PLoopEnd -> Pnext;
PLoopEnd1 = PLoop;
while (PLoopEnd1 -> Pnext != PLoopEnd) PLoopEnd1 = PLoopEnd1 -> Pnext;
if (VStart != VEnd) {
/* Now we test if we need to create a polygon formed from S & open */
/* loop by testing on which side of the polygon that caused */
/* intersection L0L1, point P2 is, and compare with requirement AinB.*/
GenClipPoly = TestAinB(VStart -> Pnext, OLoop -> PISeg -> Pl, AinB);
/* Keep the clipped VertexList P2, P3 & substitute with open loop: */
/* Note we must keep vertex VEnd in the polygon as another InterSeg. */
/* may point on it, so we replace InterSeg point (L3) by (P3) and */
/* leave VEnd intact. */
Ptemp1 = VEnd -> Pnext; /* Save that pointer temporary. */
VEnd -> Pnext = NULL; /* Close the clipped vertex list. */
PT_SWAP(VEnd -> Pt, PLoopEnd -> Pt);
PT_SWAP(VEnd -> Normal, PLoopEnd -> Normal);
VEnd1 -> Pnext = PLoopEnd;
PLoopEnd1 -> Pnext = VEnd;
PLoopEnd -> Count = VEnd -> Count;
PLoopEnd -> Tags = VEnd -> Tags;
Ptemp2 = VEnd;
VEnd = PLoopEnd;
PLoopEnd = Ptemp2;
ClipPoly = VStart -> Pnext;
/* New ClipPoly is isolated (Open loop of P2, P3 only). Save */
/* reversed list of open loop if we need to form an S/OLoop polygon, */
/* otherwise free ClipPoly. Chain the OLoop instead of S. */
if (GenClipPoly)
PRevLoop = GenReverseVrtxList(PLoop);
else
MyFree((char *) ClipPoly, ALLOC_VERTEX);
VStart -> Pnext = PLoop; /* Chain the OLoop instead of S. */
PLoopEnd -> Pnext = Ptemp1;
}
else { /* VStart == VEnd */
/* Now we test if we need to create a polygon formed from S & open */
/* loop by testing on which side of the polygon that caused */
/* intersection L0L1, point L3 is, and compare with requirement AinB.*/
GenClipPoly = TestAinB(PLoopEnd, OLoop -> PISeg -> Pl, AinB);
/* In this case the clipped part is empty, so its simpler: */
ClipPoly = NULL;
/* Save reversed list of open loop if we need to form an S/OLoop */
/* polygon. Chain the OLoop instead of S. */
if (GenClipPoly) PRevLoop = GenReverseVrtxList(PLoop);
PLoopEnd -> Pnext = VEnd -> Pnext;
PLoopEnd -> Tags = VEnd -> Tags;
VStart -> Pnext = PLoop; /* Chain the OLoop instead of S. */
}
/* Time to free the InterSegment list pointed by OLoop: */
PISeg = OLoop -> PISeg;
while (PISeg != NULL) {
PItemp = PISeg;
PISeg = PISeg -> Pnext;
MyFree((char *) PItemp, ALLOC_OTHER);
}
OLoop -> PISeg = NULL; /* To be on the safe side... */
/* There is a chance that Pl -> V will point on vertex in the clipped */
/* part so we update it to point on VStart, which for sure is in polygon.*/
Pl -> V = VStart;
if (GenClipPoly) { /* Generate the polygon from ClipPoly & PRevLoop: */
PLoopEnd = PRevLoop;
while (PLoopEnd -> Pnext != NULL) PLoopEnd = PLoopEnd -> Pnext;
if (ClipPoly == NULL) {
PLoopEnd -> Pnext = PRevLoop; /* Close that loop and return it. */
ClipPl = AllocPolygon(0, 0, PRevLoop, NULL);
PLANE_COPY(ClipPl -> Plane, Pl -> Plane);
RST_CONVEX_POLY(ClipPl); /* May be not convex now. */
return ClipPl;
}
PLoopEnd -> Pnext = ClipPoly;
PLoopEnd -> Tags = VStart -> Tags;
PLoopEnd -> Count = VStart -> Count;
Ptemp1 = ClipPoly;
while (Ptemp1 -> Pnext != NULL) Ptemp1 = Ptemp1 -> Pnext;
Ptemp1 -> Pnext = PRevLoop;
ClipPl = AllocPolygon(0, 0, ClipPoly, NULL);
PLANE_COPY(ClipPl -> Plane, Pl -> Plane);
RST_CONVEX_POLY(ClipPl); /* May be not convex now. */
return ClipPl;
}
else
return NULL;
}
/*****************************************************************************
* Find the intersection of the ray fired from Pt to +X direction with the *
* given polygon. Note Pt MUST be in the polygon. Two vertices equal to *
* ray/polygon intersection point are added to polygon vertex list, and a *
* pointer to the first one is also returned. This routine is exclusively *
* used by the CombineClosedLoops below. *
* The polygon is NOT assumed to be convex and we look for the minimum X *
* intersection. The polygon might not be convex as a result of combinning *
* some other closed loop before the current one... *
*****************************************************************************/
static VertexStruct *CutPolygonAtRay(PolygonStruct *Pl, PointType Pt)
{
int OnVertex;
RealType MinX = INFINITY, X;
VertexStruct *V, *Vnext, *VMinX = NULL;
V = Pl -> V;
do {
Vnext = V -> Pnext;
/* A polygon edge might intersect the ray iff one of the following: */
/* 1. The first vertex is exactly on the ray Y level. (if this is */
/* true for the second edge, it will be detected next iteration). */
/* 2. The first vertex is below ray Y level, and second is above. */
/* 3. The first vertex is above ray Y level, and second is below. */
if (APX_EQ(V -> Pt[1], Pt[1])) { /* Case 1 above. */
if (MinX > V -> Pt[0] && Pt[0] < V -> Pt[0]) {
OnVertex = TRUE;
MinX = V -> Pt[0];
VMinX = V;
}
}
else if ((V -> Pt[1] < Pt[1] && Vnext -> Pt[1] > Pt[1]) ||/* Case 2. */
(V -> Pt[1] > Pt[1] && Vnext -> Pt[1] < Pt[1])) {/* Case 3. */
X = ((Vnext -> Pt[1] - Pt[1]) * V -> Pt[0] +
(Pt[1] - V -> Pt[1]) * Vnext -> Pt[0]) /
(Vnext -> Pt[1] - V -> Pt[1]);
if (MinX > X && Pt[0] < X) {
OnVertex = FALSE;
MinX = X;
VMinX = V;
}
}
V = Vnext;
}
while (V != NULL && V != Pl -> V);
if ((V = VMinX) == NULL)
FatalError("CutPolygonAtRay: fail to find intersection");
/* Now that we have the intersection point - create two new vertices */
/* (one if OnVertex), insert them (it) after V and return the first. */
if (OnVertex) {
V -> Pnext = AllocVertex(V -> Count, V -> Tags, NULL, V -> Pnext);
PT_COPY(V -> Pnext -> Pt, V -> Pt);
PT_CLEAR(V -> Pnext -> Normal);
V -> Tags = V -> Count = 0;
}
else {
V -> Pnext = AllocVertex(V -> Count, V -> Tags, NULL, V -> Pnext);
Vnext = V -> Pnext;
Vnext -> Pt[0] = MinX; /* X - as intersection point found. */
Vnext -> Pt[1] = Pt[1]; /* Y - must be as ray Y level. */
Vnext -> Pt[2] = V -> Pt[2]; /* Z - all polygon has same Z value. */
V -> Pnext = AllocVertex(0, 0, NULL, V -> Pnext);
V = V -> Pnext;
PT_COPY(V -> Pt, Vnext -> Pt);
PT_CLEAR(V -> Normal);
}
return V;
}
/*****************************************************************************
* Convert the given closed loop list to polygons, and return them. the *
* original given polygon vertex list is freed, and the first loop is subst. *
* instead. *
*****************************************************************************/
static void ClosedLoopsToPolys(InterSegListStruct *PClosed, PolygonStruct *Pl)
{
int LoopNum = 0;
VertexStruct *V, *VHead;
InterSegmentStruct *PISeg, *PItemp;
InterSegListStruct *PClosedTemp;
MyFree((char *) Pl -> V, ALLOC_VERTEX);
Pl -> Pnext = NULL;
SET_INOUTPUT_POLY(Pl); /* Mark the polygon as in output. */
while (PClosed != NULL) {
/* Convert the InterList to vertex list and free the first: */
V = VHead = InterLoopToVrtxList(PClosed -> PISeg);
if (V -> Pnext == NULL || V -> Pnext -> Pnext == NULL)
FatalError("ClosedLoopsToPolys: Closed loop with less than 3 vertices");
PISeg = PClosed -> PISeg; /* Time to free the InterSegmentList: */
while (PISeg != NULL) {
PItemp = PISeg;
PISeg = PISeg -> Pnext;
MyFree((char *) PItemp, ALLOC_OTHER);
}
while (V -> Pnext -> Pnext != NULL) V = V -> Pnext; /* Go to last pt */
MyFree((char *) V -> Pnext, ALLOC_VERTEX);/*and free - same as first.*/
V -> Pnext = VHead; /* Make vertex list circular. */
if (LoopNum++) {
Pl -> Pnext = AllocPolygon(0, 0, VHead, Pl -> Pnext);
PLANE_COPY(Pl -> Pnext -> Plane, Pl -> Plane);
}
else {
Pl -> V = VHead;
}
PClosedTemp = PClosed;
PClosed = PClosed -> Pnext;
MyFree((char *) PClosedTemp, ALLOC_OTHER);
}
}
/*****************************************************************************
* This routines cuts the given polygon into its interior closed loops by *
* adding an edge from the polygon boundary to each of its closed loops. *
* For example: *
* *
* +-----------------------+ +-----------------------+ *
* | | | | *
* | / \ / \ | | / \________ / \ | *
* | \ / | | | | \ / | |_____| *
* | _ \ / | --> | _ \ / | *
* | / \_ | --> | / \_ | *
* | | | | | | |_____________| *
* | \__/ | | \__/ | *
* | | | | *
* +-----------------------+ +-----------------------+ *
* *
* Algorithm: *
* 1. Transform the polygon and the closed loops to a plane parallel to XY *
* plane (Z = Const plane). *
* 2. For each loop find its MaxX while keeping the information on the *
* vertex on that extremum. *
* 3. For the loop with the biggest MaxX: *
* 3.1. Use that extremum vertex (which must be non concave corner) to *
* test if loop is in the reverse direction the polygon itself is, *
* and reverse it if not. *
* 3.2. Fire a ray from the extremum vertex, to the +X direction outside *
* of the loop till it intersect the polygon, break the polygon at *
* that point and add two edges to beginning of loop from breaking *
* point and from end of loop to breaking point (beginning/end point *
* of loop is the extremum vertex point). *
* 4. Repeat step 3, with all loops. *
* 5. Transfrom the new polygon back (using the inverse matrix of step 1) *
* to its original orientation. *
* *
* Returns TRUE iff the original polygon boundary is in output. *
* *
*****************************************************************************/
static int CombineClosedLoops(PolygonStruct *Pl, InterSegListStruct *PClosed,
int AinB)
{
RealType MaxX;
PointType V1, V2, Normal, PlNormal;
MatrixType RotMat;
VertexStruct *V, *Vnext, *Vprev, *VHead, *VMaxX, VStruct;
InterSegListStruct *PClosedTemp, *PClosedMaxX, *PClosedLast,
*PClosedMaxXLast;
InterSegmentStruct *PISeg, *PItemp, *PISegMaxX;
Pl -> Pnext = NULL; /* Make sure this polygon is disconnected. */
/* Stage 1 - Transform the vertices to a plane parallel to XY plane: */
GenRotateMatrix(RotMat, Pl -> Plane);
V = VHead = Pl -> V;
do { /* Transform the polygon itself. */
MatMultVecby4by4(V -> Pt, V -> Pt, RotMat);
V = V -> Pnext;
}
while (V != NULL && V != VHead);
PClosedTemp = PClosed;
while (PClosedTemp != NULL) { /* And transform the loops also. */
PISeg = PClosed -> PISeg;
while (PISeg != NULL) {
MatMultVecby4by4(PISeg -> PtSeg[0], PISeg -> PtSeg[0], RotMat);
MatMultVecby4by4(PISeg -> PtSeg[1], PISeg -> PtSeg[1], RotMat);
PISeg = PISeg -> Pnext;
}
PClosedTemp = PClosedTemp -> Pnext;
}
if (!MatInverseMatrix(RotMat, RotMat)) /* Find the inverse matrix. */
FatalError("CombineClosedLoops: Inverse matrix does not exists");
/* Evalaute the normal to the polygon (which must be convex!). Note we */
/* cannt simply use the Plane normal as the polygon was transformed. */
V = Pl -> V;
do {
Vnext = V -> Pnext;
PT_SUB(V1, Vnext -> Pt, V -> Pt);
PT_SUB(V2, Vnext -> Pnext -> Pt, Vnext -> Pt);
VecCrossProd(PlNormal, V1, V2);
V = Vnext;
}
while (PT_LENGTH(PlNormal) < EPSILON);
PClosedTemp = PClosed;
while (PClosedTemp != NULL) {
/* Stage 2 - find MaxX extremum value of given loop, test the loop */
/* direction, and reverse it if wrong. Note we convert the loop */
/* given as InterSegListStruct list into VertexStruct list first. */
PISegMaxX = PISeg = PClosedTemp -> PISeg;
MaxX = PISeg -> PtSeg[0][0]; /* Get first vertex X val. */
PISeg = PISeg -> Pnext;
while (PISeg)
{
if (PISeg -> PtSeg[0][0] > MaxX) {
MaxX = PISeg -> PtSeg[0][0];
PISegMaxX = PISeg;
}
PISeg = PISeg -> Pnext;
}
PClosedTemp -> PISegMaxX = PISegMaxX;
PClosedTemp = PClosedTemp -> Pnext;
}
/* Stage 3/4 - find the loop with biggest MaxX and combine it with the */
/* polygon itself. Do it for all closed loops, in list: */
PClosedTemp = PClosed;
while (PClosed != NULL) {
/* Find the one with maximum MaxX, and delete it from PClosed list. */
PClosedLast = PClosedMaxX = PClosedTemp = PClosed;
MaxX = PClosedMaxX -> PISegMaxX -> PtSeg[0][0];
while (PClosedTemp != NULL)
{
if (PClosedTemp -> PISegMaxX -> PtSeg[0][0] > MaxX) {
PClosedMaxX = PClosedTemp;
PClosedMaxXLast = PClosedLast;
}
PClosedLast = PClosedTemp;
PClosedTemp = PClosedTemp -> Pnext;
}
if (PClosedMaxX == PClosed)
PClosed = PClosed -> Pnext; /* Del. from */
else
PClosedMaxXLast -> Pnext = PClosedMaxX -> Pnext; /* PClosed list.*/
/* Create a vertex list from the loop: */
V = VHead = InterLoopToVrtxList(PClosedMaxX -> PISeg);
if (V -> Pnext == NULL || V -> Pnext -> Pnext == NULL)
FatalError("CombineClosedLoops: Closed loop with less than 3 vertices");
V = VHead;
while (V -> Pnext -> Pnext != NULL) V = V -> Pnext; /* Go to last pt */
MyFree((char *) V -> Pnext, ALLOC_VERTEX);/*and free - same as first.*/
V -> Pnext = VHead; /* Make vertex list circular. */
PISegMaxX = PClosedMaxX -> PISegMaxX;
/* Now test if the vertex list should be reversed. Find the vertices */
/* which form the PISegMaxX segment, so V -> Pnext is the first */
/* vertex in PISegMaxX segment. Then the 3 vertices V , V -> Pnext */
/* (on PISegMaxX), V -> Pnext -> Pnext (on PISegMaxX), must form */
/* convex corner which we use to test if loop needs to be reversed: */
while (!PT_EQ(V -> Pnext -> Pt, PISegMaxX -> PtSeg[0]))
V = V -> Pnext;
VMaxX = V -> Pnext;
PT_COPY(VStruct.Pt, V -> Pt); /* Prepare in point in REAL position. */
MatMultVecby4by4(VStruct.Pt, VStruct.Pt, RotMat);
VStruct.Pnext = NULL;
if (TestAinB(&VStruct, PISegMaxX -> Pl, AinB)) {
/* The Inside of the object is actually the loop itself. In that */
/* case we simply return all the loops converted into polygon. */
/* This case is simple... */
MyFree((char *) VHead, ALLOC_VERTEX); /* Free loop vertex list. */
PClosedMaxX -> Pnext = PClosed;/* Put back first loop into list. */
PClosedTemp = PClosed = PClosedMaxX;
while (PClosedTemp != NULL) { /* Transform the loops back. */
PISeg = PClosed -> PISeg;
while (PISeg != NULL) {
MatMultVecby4by4(PISeg -> PtSeg[0], PISeg -> PtSeg[0], RotMat);
MatMultVecby4by4(PISeg -> PtSeg[1], PISeg -> PtSeg[1], RotMat);
PISeg = PISeg -> Pnext;
}
PClosedTemp = PClosedTemp -> Pnext;
}
ClosedLoopsToPolys(PClosedMaxX, Pl);/* And convert them to polys.*/
return FALSE; /* Boundary is NOT part of object result. */
}
PT_SUB(V1, VMaxX -> Pt, V -> Pt);
PT_SUB(V2, VMaxX -> Pnext -> Pt, VMaxX -> Pt);
VecCrossProd(Normal, V1, V2);
if (DOT_PROD(Normal, PlNormal) > 0) { /* Need to reverse list. */
Vprev = VHead;
V = Vprev -> Pnext;
Vnext = V -> Pnext;
do {
V -> Pnext = Vprev;/* Reverse to point on prev instead next. */
Vprev = V;
V = Vnext;
Vnext = V -> Pnext;
}
while (Vprev != VHead);
}
PISeg = PClosedMaxX -> PISeg; /* Time to free the InterSegmentList: */
while (PISeg != NULL) {
PItemp = PISeg;
PISeg = PISeg -> Pnext;
MyFree((char *) PItemp, ALLOC_OTHER);
}
MyFree((char *) PClosedMaxX, ALLOC_OTHER);
/* O.k. lets fire a ray from VMaxX to +X direction and see where it */
/* intersects the polygon. The routine CutPolygonAtRay will add two */
/* vertices at the ray intersection into polygon vertex list and */
/* return a pointer to first one, so we can chain our loop directly */
/* between these two new vertices. */
V = CutPolygonAtRay(Pl, VMaxX -> Pt);
Vnext = V -> Pnext;
/* Introduce a copy of VMaxX and successor to VMaxX: */
VMaxX -> Pnext = AllocVertex(VMaxX -> Count, VMaxX -> Tags, NULL,
VMaxX -> Pnext);
PT_COPY(VMaxX -> Pnext -> Pt, VMaxX -> Pt);
PT_CLEAR(VMaxX -> Pnext -> Normal);
V -> Pnext = VMaxX -> Pnext;
SET_INTERNAL_EDGE(V);
VMaxX -> Pnext = Vnext;
SET_INTERNAL_EDGE(VMaxX);
}
/* Stage 5 - Time to rotate polygon back to its original position. */
V = VHead = Pl -> V;
do {
MatMultVecby4by4(V -> Pt, V -> Pt, RotMat);
V = V -> Pnext;
}
while (V != NULL && V != VHead);
SET_INOUTPUT_POLY(Pl); /* Mark the polygon as in output. */
RST_CONVEX_POLY(Pl); /* This polygon is not convex any more. */
return TRUE;
}
/*****************************************************************************
* Push on the adjacency stack, all adjacent polygons which are complete *
* (no intersection) and are adjacent to complete edges (originated from *
* input polygons) of the given polygon. *
*****************************************************************************/
static void PushAdjOnStack(PolygonStruct *Pl, PolygonStruct *AdjStack[],
int *StackPointer)
{
VertexStruct *V = Pl -> V;
do {
/* If you wants to propagate iff both vertices are original then */
/* uncomment the next line. */
if (IS_ORIGINAL_VRTX(V) /* && IS_ORIGINAL_VRTX(V -> Pnext) */
&& V -> PAdj != NULL)
AdjStack[++*StackPointer] = V -> PAdj;
if (*StackPointer >= ADJ_STACK_SIZE) {
FatalError("Adjacency stack overflow, object too big\n");
}
V = V -> Pnext;
}
while (V != Pl -> V);
}
/*****************************************************************************
* Chain two Polygon lists into one. For fast processing it is prefered the *
* first one to be to shorter. Returns pointer to chained list. *
*****************************************************************************/
static PolygonStruct *ChainPolyLists(PolygonStruct *Pl1, PolygonStruct *Pl2)
{
PolygonStruct *Ptemp;
if (Pl1 == NULL)
return Pl2;
else if (Pl2 == NULL)
return Pl1;
else {
Ptemp = Pl1;
while (Ptemp -> Pnext != NULL) Ptemp = Ptemp -> Pnext;
Ptemp -> Pnext = Pl2;
return Pl1;
}
}
/*****************************************************************************
* This routine coordinates all the extraction of the polygons from the *
* intersecting lists. Does it in the following steps: *
* 1. Mark all polygons with no intersection at all as complete polygons. *
* (this is cause that this polygon will be totally in or out, according *
* to inter-polygon adjacencies propagation...) *
* Also Mark them as undefined (if in output or undefined) yet. *
* Uses PolygonStruct Tags to save these bits. *
* 2. 2.1. Convert the unordered segment list of each polygon to closed loops *
* (if create a hole in polygon) or open (if crosses its boundary). *
* 2.2. Order the open loops along the perimeter of the polygon (note *
* these loops cannt intersect. For example (5 vertices polygon): *
* -----------------------------L3 *
* | ---------------L1 -----L2 | --------L4 --L5 *
* | | | | | | | | | | *
* P0 ------ P1 ------- P2 ----- P3 -------- P4 ------ P5 -------- P0 *
* Note L1, L2 are enclosed in L3 loop, and that the order is circular*
* 2.3. "Break" the polygon at each open loop that has no enclosed loops *
* in it. For example we can start at L1, L2, L4, L5 and then L3. *
* "Break" means - replace the vertex chain between the two loop end *
* points, with the loops itself. Depends upon the relation required *
* we may need to output a new polygon form from the deleted chain *
* and that loop. In addition we may form a new polygon from last *
* loop and was was left from the original polygon *
* For each formed polygon, for each complete edge of it (i.e. edge *
* which was originally in the polygon) test the adjacent polygon *
* if it is complete (as marked in 1.) and if in or undefined (marked *
* undefined in 1.) is still undefined: *
* 2.3.1. set it to be in. *
* 2.3.2. push it on adjacency stack. *
* 2.4. For each closed loop - find in which polygon (from polygons *
* created in 2.3.) it is enclosed, and decompose it. *
* 3. While adjacencies stack not empty do: *
* 3.1. pop top polygon from stack and output it. *
* 3.2. For each of its edges (which obviousely must be complete edges) *
* if adjacent polygon is complete and undefined: *
* 3.3.1. set it to be in. *
* 3.3.2. push it on adjacency stack. *
* 3.3 go back to 3. *
* *
* The above algorithm defines in as in output, but dont be confused with *
* the required inter-object AinB (or AoutB if FALSE), which used to *
* determine which side of the trimming loop should be output. *
* Note this routine may return non-convex polygons (but marked as so) even *
* though the input for the booleans must be convex polygons only! *
* In order to keep the given object unchanged, a whole new copy off the *
* polygon list is made. The polygons of the list that are not in the output *
* are freed: a global list of all polygons (pointers) is used to scan them *
* in the end and free the unused ones (list PolysPtr). *
*****************************************************************************/
ObjectStruct *ExtractPolygons(ObjectStruct *PObj, int AinB)
{
int NumOfPolys = 0, StackPointer = -1;
PolygonStruct *AdjStack[ADJ_STACK_SIZE], **PolysPtr, *OriginalPl,
*Pl, *PlHead, *PlNext, *OutputPl = NULL, *SplPl, *NewPl;
VertexStruct *V, *Vnext;
InterSegListStruct *PClosed, *POpen, *Ptemp;
#ifdef DEBUG3
printf("Enter ExtractPolygons\n");
#endif /* DEBUG3 */
TestBooleanCtrlBrk();
/* Stage 1. - mark all polygons as needed: */
PlHead = Pl = PObj -> U.Pl.P;
/* Gen. a copy of Pl, so we can modify the original polygon list: */
PObj -> U.Pl.P = CopyPolygonList(Pl);
while (Pl != NULL) {
NumOfPolys++; /* Count number of polygons in original object. */
if (Pl -> PAux != NULL) { /* The intersection list is not empty! */
RST_COMPLETE_POLY(Pl); /* Mark it as non complete polygon. */
V = Pl -> V;
do {
SET_ORIGINAL_VRTX(V); /* Mark vertices from original object. */
V = V -> Pnext;
}
while (V != Pl -> V);
}
else {
SET_COMPLETE_POLY(Pl); /* Mark it as complete polygon. */
RST_INOUTPUT_POLY(Pl); /* And as undefined (if in output). */
RST_ADJPUSHED_POLY(Pl); /* And as not pushed on adj. stack. */
}
Pl = Pl -> Pnext;
}
/* Stage 2. - scan the polygons and subdivide the intersecting ones: */
Pl = PlHead;
/* We will save pointers to ALL polygons in list so we could free in the */
/* end the ones that are not in the output list, and therefore unused. */
PolysPtr = (PolygonStruct **)
MyMalloc(sizeof(PolygonStruct *) * NumOfPolys, ALLOC_OTHER);
NumOfPolys = 0;
while (Pl != NULL) {
TestBooleanCtrlBrk();
PolysPtr[NumOfPolys++] = Pl; /* Save pointer to this polygon. */
PlNext = Pl -> Pnext;
Pl -> Pnext = NULL;
if (!IS_COMPLETE_POLY(Pl)) {/* They are intersections with this one. */
/* Convert the intersecting segments into open/closed loops. */
LoopsFromInterList(Pl, &PClosed, &POpen);
/* Save copy of original polygon vertex list as we need its */
/* normals to interpolate for the internal ones. */
OriginalPl = AllocPolygon(1, Pl -> Tags, CopyVList(Pl -> V), NULL);
PLANE_COPY(OriginalPl -> Plane, Pl -> Plane);
if (POpen != NULL) {
/* Sort the Open loops into an order we can handle... */
SortOpenInterList(Pl, &POpen);
SplPl = NewPl = NULL; /* Keep the list of split polygons. */
while (POpen != NULL) { /* Clip the open loops from polygon: */
/* Note ClipOpenLoopFromPoly also frees the InterSegment */
/* list pointed by POpen (but not POpen itself). */
NewPl = ClipOpenLoopFromPoly(Pl, POpen, AinB);
if (NewPl != NULL) { /* If loop clipped a new polygon, */
PLANE_COPY(NewPl -> Plane, OriginalPl -> Plane);
NewPl -> Pnext = SplPl;/* add to split polygon list. */
SplPl = NewPl;
/* And push adj. polygons of complete edges on stack.*/
PushAdjOnStack(NewPl, AdjStack, &StackPointer);
}
Ptemp = POpen;
POpen = POpen -> Pnext;
MyFree((char *) Ptemp, ALLOC_OTHER);
}
/* Last clip generated nothing (NewPl == NULL) so part that */
/* left from Pl (PlCopy) is IN output list! Add this poly: */
if (NewPl == NULL) {
PLANE_COPY(Pl -> Plane, OriginalPl -> Plane);
Pl -> Pnext = SplPl; /* And chain what was left from it. */
SplPl = Pl;
/* And push adjacent polygons of complete edges on stack.*/
PushAdjOnStack(Pl, AdjStack, &StackPointer);
SET_INOUTPUT_POLY(Pl);/* So we wouldnt free that in end. */
RST_CONVEX_POLY(Pl); /* May be not convex now. */
}
UpdateVerticesNormals(SplPl, OriginalPl);
}
else
SplPl = Pl;
if (PClosed != NULL) {
for (Pl = SplPl; Pl != NULL; Pl = Pl -> Pnext)
Pl -> PAux = NULL;
/* Classify the closed loops into the appropriate polygon. */
while (PClosed != NULL) {
Ptemp = PClosed -> Pnext;
for (Pl = SplPl; Pl != NULL; Pl = Pl -> Pnext) {
if (CGPolygonRayInter3D(Pl, PClosed -> PISeg -> PtSeg[0],
0) % 2 == 1) {
/* This closed loop is contained in this polygon.*/
PClosed -> Pnext = (InterSegListStruct *) Pl -> PAux;
Pl -> PAux = (VoidPtr) PClosed;
break;
}
}
if (Pl == NULL) {
/* This closed loop is part of a trimmed out by open */
/* loop region. It should be only the island formed */
/* by this closed loop then. */
/* Make a new polygon - a copy of the original and */
/* Put this loop in it. */
NewPl = AllocPolygon(1, OriginalPl -> Tags,
CopyVList(OriginalPl -> V), NULL);
PLANE_COPY(NewPl -> Plane, OriginalPl -> Plane);
NewPl -> PAux = (VoidPtr) PClosed;
NewPl -> Pnext = SplPl;
SplPl = NewPl;
}
PClosed = Ptemp;
}
for (Pl = SplPl; Pl != NULL; Pl = Pl -> Pnext) {
/* Make a "cut" from the loop(s) +-------+ +-------+ */
/* to boundary if possible, and | | | | */
/* converting Pl to a nonconvex | / \ | -> | / \__| */
/* polygon, that has an edge (the | \ / | -> | \ / | */
/* cut) which is shared twice in | | | | */
/* the same polygon +-------+ +-------+ */
PClosed = (InterSegListStruct *) Pl -> PAux;
Pl -> PAux = NULL;
if (CombineClosedLoops(Pl, PClosed, AinB)) {
/* If returned with TRUE - polygon boundary is in */
/* output, so add all its neighbours to adj. stack. */
PushAdjOnStack(Pl, AdjStack, &StackPointer);
}
UpdateVerticesNormals(Pl, OriginalPl);
}
}
OutputPl = ChainPolyLists(SplPl, OutputPl);
/* Free the original polygon vertex list. */
MyFree((char *) OriginalPl, ALLOC_POLYGON);
}
Pl = PlNext;
}
/* Stage 3. - handling adjacencies and propagate them in polygons: */
/* Pop off the elements from the stack, and propagate them using their */
/* adjacencies. */
while (StackPointer >= 0) {
Pl = AdjStack[StackPointer--]; /* Pop top element. */
if (!IS_COMPLETE_POLY(Pl) || /* Ignore non complete polygons. */
IS_INOUTPUT_POLY(Pl)) continue; /* If already handled. */
SET_INOUTPUT_POLY(Pl); /* Mark this one as handled for next time. */
V = Pl -> V; /* Push all adjacent ones that not handled yet. */
do {
if (V -> PAdj &&
IS_COMPLETE_POLY(V -> PAdj) &&
!IS_INOUTPUT_POLY(V -> PAdj) &&
!IS_ADJPUSHED_POLY(V -> PAdj)) {
SET_ADJPUSHED_POLY(V -> PAdj);
AdjStack[++StackPointer] = V -> PAdj; /* Push it on stack. */
if (StackPointer >= ADJ_STACK_SIZE)
FatalError("Adjacency stack overflow, object too big\n");
}
V = V -> Pnext;
}
while (V != Pl -> V);
Pl -> Pnext = OutputPl; /* And chain it into output list. */
OutputPl = Pl;
}
/* Free all polygons which are not in the output list: */
while (--NumOfPolys >= 0) {
if (!IS_INOUTPUT_POLY(PolysPtr[NumOfPolys])) {
PolysPtr[NumOfPolys] -> Pnext = NULL; /* Free only this polygon. */
MyFree((char *) (PolysPtr[NumOfPolys]), ALLOC_POLYGON);
}
}
MyFree((char *) PolysPtr, ALLOC_OTHER);
/* Another floating point kludge: a polygon may have zero length edge so */
/* search for those and remove them - someone may die because of one... */
Pl = OutputPl;
while (Pl != NULL) {
V = Pl -> V;
do {
Vnext = V -> Pnext;
if (PT_EQ(V -> Pt, Vnext -> Pt)) {
/* Ahh - we got you. Simply skip Vnext vertex and free it: */
V -> Pnext = Vnext -> Pnext;
/* Update polygon vertex pointer if point on freed vertex: */
if (Pl -> V == Vnext) Pl -> V = Vnext -> Pnext;
Vnext -> Pnext = NULL; /* Dont free too much! */
MyFree((char *) Vnext, ALLOC_VERTEX);
Vnext = V -> Pnext;
}
V = Vnext;
}
while (V != Pl -> V && V != NULL);
Pl = Pl -> Pnext;
}
#ifdef DEBUG3
printf("Exit ExtractPolygons\n");
#endif /* DEBUG3 */
return GenPolyObject("", OutputPl, NULL); /* Return resulting object. */
}
#ifdef DEBUG2
/*****************************************************************************
* Print the content of the given polygon, to standard output. *
*****************************************************************************/
static void PrintVrtxList(VertexStruct *V)
{
VertexStruct *VHead = V;
do {
printf(" %12lf %12lf %12lf", V -> Pt[0], V -> Pt[1], V -> Pt[2]);
if (IS_INTERNAL_EDGE(V))
printf(" (Internal)\n");
else
printf("\n");
V = V -> Pnext;
}
while (V!= NULL && V != VHead);
}
/*****************************************************************************
* Print the content of the given InterSegment list, to standard output. *
*****************************************************************************/
static void PrintInterList(InterSegmentStruct *PInt)
{
printf("INTER SEGMENT LIST:\n");
if (PInt) printf("Entry vertex pointer %p\n", PInt -> V[0]);
while (PInt) {
printf("%9lg %9lg %9lg (%04x), %9lg %9lg %9lg (%04x)\n",
PInt->PtSeg[0][0], PInt->PtSeg[0][1], PInt->PtSeg[0][2],
FP_SEG(PInt->V[0]),
PInt->PtSeg[1][0], PInt->PtSeg[1][1], PInt->PtSeg[1][2],
FP_SEG(PInt->V[1]));
if (PInt -> Pnext == NULL)
printf("Exit vertex pointer %p\n", PInt -> V[1]);
PInt = PInt -> Pnext;
}
}
#endif /* DEBUG2 */